package com.geek.sort;

/**
 * 快速排序法(其实就是分区排序)
 * 先拿一个基准值(拿最左边最右边或者中间都行)
 * 比如左边作为基准值，然后从第二个元素开始一直比较到区间right结束
 * 判断小的就和从i交换位置，然后i++(这里的i是从左边+1开始算的，目的是为了判断挪移的数量，确定下一个区间的中间下标)
 * 一次循环挪完数据之后，将最左边的值与i交换位置，保证区间值在中间，然后进行递归
 * https://www.runoob.com/w3cnote/quick-sort-2.html
 */
public class QuickSort {

	public static void main(String[] args) {
		int[] arr = new int[]{10, 5, 3, 2, 4, 8, 6, 7};

		QuickSort sort = new QuickSort();
		sort.sort(arr, 0, arr.length-1);

		printArr(arr);
	}


	/**排序方法*/
	private void sort(int[] arr, int left, int right) {
		if(left < right){
			int i = partition(arr, left, right);
			sort(arr, left, i-1);
			sort(arr, i, right-1);
		}
	}


	/**
	 * 分区
	 * @param arr   入参数组
	 * @param left   区间左边
	 * @param right  区间右边
	 * @return      返回区间里面排序之后的下标
	 */
	private int partition(int[] arr, int left, int right){
		int pivot = arr[left];
		int i = left;
		for(int j = left+1; j <= right; j++){
			if (arr[j] <= pivot){
				i++;
				swap(arr, i, j);
			}
		}
		swap(arr, left, i);
		return i;
	}

	void swap(int[] arr, int i, int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	private static void printArr(int[] arr){
		for (int value : arr) {
			System.out.print(value + ",");
		}
		System.out.println();
	}

}
